package com.zhj.leetcode;

import sun.util.resources.cldr.mas.LocaleNames_mas;

/**
 * 力扣42
 * 接雨水
 * @author zhj
 * @create 2024-02-19-15:19
 */
public class Test42 {

    public static void main(String[] args) {
        int[] height = new int[]{0,1,0,2,1,0,1,3,2,1,2,1};
        System.out.println(trap3(height));
    }

    /**
     * 暴力
     * @param height
     * @return
     */
    public static int trap1(int[] height) {
        int ans = 0;
        int len = height.length;
        for (int i = 1; i < len - 1; i++) {
            int l_max = 0;
            int r_max = 0;
            for (int j = i; j < len; j++) {
                r_max = Math.max(r_max, height[j]);
            }

            for (int j = i; j >= 0; j--) {
                l_max = Math.max(l_max, height[j]);
            }
            ans += Math.min(l_max, r_max) - height[i];
        }
        return ans;
    }

    /**
     * 备忘录
     * @param height
     * @return
     */
    public static int trap2(int[] height) {
        int ans = 0;
        int len = height.length;
        int[] l_max = new int[len];
        int[] r_max = new int[len];
        l_max[0] = height[0];
        r_max[len-1] = height[len - 1];
        for (int i = 1; i < len; i++) {
            l_max[i] = Math.max(l_max[i-1], height[i]);
        }
        for (int i = len-2; i >= 0; i--) {
            r_max[i] = Math.max(r_max[i+1], height[i]);
        }
        for (int i = 1; i < len; i++) {
            ans += Math.min(l_max[i], r_max[i]) - height[i];
        }
        return ans;
    }

    /**
     * 双指针
     * @param height
     * @return
     */
    public static int trap3(int[] height) {
        int ans = 0;
        int l = 0;
        int r = height.length - 1;
        int l_max = 0;
        int r_max = 0;
        while (l < r) {
            l_max = Math.max(l_max, height[l]);
            r_max = Math.max(r_max, height[r]);
            if (l_max < r_max) {
                ans += l_max -height[l];
                l++;
            } else {
                ans += r_max -height[r];
                r--;
            }
        }
        return ans;
    }
}
